/**
 * 
 */
package leetCode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author zhongfang
 *
 */
public class NextGreaterElementII {
    public static int[] nextGreaterElements(int[] nums) {
        if(nums.length==0){
            return new int[0];
        }
        int[] result=new int[nums.length];
        HashMap<Integer,Integer> hm=new HashMap<>();
        Stack<Integer> s=new Stack<>();
        LinkedList<Integer> list=new LinkedList<>();
        for(int i=0;i<nums.length;i++){
            while(!s.isEmpty()&&nums[s.peek()]<nums[i]){
                hm.put(s.pop(),nums[i]);
            }
            s.add(i);
            if(list.isEmpty()||nums[i]>nums[list.getLast()]){
            	list.add(i);
            }
        }
        
        //栈内元素的next要在list中寻找
        while (!s.isEmpty()) {
			int tmp=s.pop();
			boolean findNxt=false;
			for (Integer integer : list) {
				if(nums[integer]>nums[tmp]){
					hm.put(tmp, nums[integer]);
					findNxt=true;
					break;
				}
			}
			if(!findNxt){
				hm.put(tmp, -1);
			}
		}
        for(int i=0;i<nums.length;i++){
            result[i]=hm.get(i);
        }
        return result;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a=new int[]{1,2,1};
		a=nextGreaterElements(a);
		for (int i : a) {
			System.out.println(i);
		}
		
	}

}
